package algorithm.slidingWindow;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class MinCoinsOnePaper {

    public static int ways(int[] arr, int aim) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i]))
                map.put(arr[i], map.get(arr[i]) + 1);
            else
                map.put(arr[i], 1);
        }
        int[] coins = new int[map.size()];
        int[] zhangs = new int[map.size()];
        int index = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            coins[index] = entry.getKey();
            zhangs[index++] = entry.getValue();
        }


        int[][] dp = new int[coins.length + 1][aim + 1];
        int N = dp.length;
        int K = dp[0].length;
        for (int i = 1; i < K; i++) {
            dp[N - 1][i] = Integer.MAX_VALUE;
        }

        for (int i = N - 2; i >= 0; i--) {
            for (int j = 0; j < K; j++) {

                int min = Integer.MAX_VALUE;
                for (int num = 0; num <= zhangs[i] && j - coins[i] * num >= 0; num++) {
                    if (dp[i + 1][j - coins[i] * num] != Integer.MAX_VALUE)
                        min = Math.min(min, dp[i + 1][j - coins[i] * num] + num);
                }
                dp[i][j] = min;
            }
        }

        return dp[0][aim];
    }


    public static int ways2(int[] arr, int aim) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i]))
                map.put(arr[i], map.get(arr[i]) + 1);
            else
                map.put(arr[i], 1);
        }
        int[] coins = new int[map.size()];
        int[] zhangs = new int[map.size()];
        int index = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            coins[index] = entry.getKey();
            zhangs[index++] = entry.getValue();
        }


        int[][] dp = new int[coins.length + 1][aim + 1];
        int N = dp.length;
        int K = dp[0].length;
        for (int i = 1; i < K; i++) {
            dp[N - 1][i] = Integer.MAX_VALUE;
        }

        for (int i = N - 2; i >= 0; i--) {
//            if (coins[i] > aim) {
//                for (int k = 0; k < K; k++) {
//                    dp[i][k] = dp[i + 1][k];
//                }
//            } else
            {
                for (int h = 0; h < Math.min(coins[i], aim + 1); h++) {
                    LinkedList<Integer> queue = new LinkedList<>();
                    for (int c = h; c <= aim; c = c + coins[i]) {
                        while (!queue.isEmpty() && (dp[i + 1][queue.peekLast()] == Integer.MAX_VALUE
                                || dp[i + 1][queue.peekLast()] + compensate(queue.peekLast(), c, coins[i]) >= dp[i + 1][c])) {
                            queue.pollLast();
                        }
                        queue.addLast(c);

                        if (queue.peekFirst() == c - (zhangs[i] + 1) * coins[i])
                            queue.pollFirst();
                        dp[i][c] = dp[i + 1][queue.peekFirst()] + compensate(queue.peekFirst(), c, coins[i]);
                    }
                }
            }
        }

        return dp[0][aim];
    }

    public static int compensate(int pre, int cur, int coin) {
        return (cur - pre) / coin;
    }


    public static int minCoins(int[] arr, int aim) {
        return process(arr, 0, aim);
    }

    public static int process(int[] arr, int index, int rest) {
        if (rest < 0) {
            return Integer.MAX_VALUE;
        }
        if (index == arr.length) {
            return rest == 0 ? 0 : Integer.MAX_VALUE;
        } else {
            int p1 = process(arr, index + 1, rest);
            int p2 = process(arr, index + 1, rest - arr[index]);
            if (p2 != Integer.MAX_VALUE) {
                p2++;
            }
            return Math.min(p1, p2);
        }
    }

    // 为了测试
    public static int[] randomArray(int N, int maxValue) {
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = (int) (Math.random() * maxValue) + 1;
        }
        return arr;
    }

    // 为了测试
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int maxLen = 20;
        int maxValue = 30;
        int testTime = 300000;
        System.out.println("功能测试开始");
        for (int i = 0; i < testTime; i++) {
            int N = (int) (Math.random() * maxLen);
            int[] arr = randomArray(N, maxValue);
            int aim = (int) (Math.random() * maxValue);
            int ans1 = ways(arr, aim);
            int ans2 = ways2(arr, aim);
            if (ans1 != ans2) {
                System.out.println("Oops!");
                printArray(arr);
                System.out.println(aim);
                System.out.println(ans1);
                System.out.println(ans2);
                break;
            }
        }
        System.out.println("功能测试结束");


//        int[] arr = {1,2,1,3,4,3};
//        int ways = ways2(arr, 6);
//        System.out.println(ways);
    }
}
